Message routing is a function that enables a network user program (or agent) to send a message to another user program. Packet communication systems do not reserve transmission facilities for the duration of a session, but only reserve individual links in the transmission path, and only for the duration of a packet. It is therefore necessary to provide a mechanism for routing digital packets through the packet network. All packet communications networks utilize a header, preceding the data packet, which contains sufficient information to control the routing of that packet from the origin of the packet to the destination of the packet.
Many routing mechanisms have been evolved in the prior art packet networking technologies. For example, Automatic Network Routing (ANR), requires the pre-calculation of the entire route from origin to destination, and identifying each link in this route in the packet header. At each intermediate node along the route, the identification of the previous link is stripped away from the header to expose the identification of the next link in the route. Message broadcasting, or multi-casting, on the other hand, utilizes a single identification of a multi-cast tree in the header and, at each intermediate node, utilizes the tree identifier to select the outgoing link or links which are included in the multi-cast tree. Yet other routing algorithms utilize the destination address in the header to select, using a routing table, the next link in the route. Note that all of these prior art routing schemes require the pre-definition of the route, either for the ANR link identifiers, the multi-cast tree definition or the routing table contents.
In many applications, the determination of the links in a route from origin to destination is preferably deferred until after the packet is launched on the network. Alternate routing in the face of link failures or to avoid congested nodes, for example, are two situations where deferred routing might be desirable. In addition to alternate routing, it may be desirable to perform other intermediate processing of a packet during the transit from origin to destination. It may, for example, be desirable to transform the data to a new format for transmission on particular links, and it may also be desirable to log and authenticate entry into foreign networks at the gateways to such foreign networks for separate billing and for network support from different network owners. Finally, address directories may be used along the route to resolve destination names or addresses in view of the content of the data, e.g., routing "800" telephone numbers or routing credit card transactions based on credit card numbers. Routing flexibility's such as those described above are important for many real time applications. Unfortunately, all of the prior art schemes for providing routing flexibility in a packet network are application-dependent, thus requiring separate routing mechanisms for different transaction codes or different user identifications. Since there is no upper bound on the number of such routable data objects, the complexity of the routing mechanisms can likewise grow without bounds.